package offer;
@FunctionalInterface

public interface CountMaxOrSubsets {
    int countMaxOrSubsets(int[] nums);
}

class CountMaxOrSubsetsTest{
    static final int[] TEST_01 = new int[]{2,2,2};
    public static void main(String[] args) {
        new CountMaxOrSubsetsImpl1().countMaxOrSubsets(TEST_01);
    }
}

class CountMaxOrSubsetsImpl1 implements CountMaxOrSubsets{
    static int count;
    static int max;
    /**
     * 穷举来一遍，时间o(n*2^n)
     */
    @Override
    public int countMaxOrSubsets(int[] nums) {
        if(nums.length == 1){
            return 1;
        }
        count = 0;
        max = Integer.MIN_VALUE;
        int n = nums.length;
        /*
        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            set.add(num);
        }

        int n = set.size(), count = 0;
        for(int num : set){
            nums[count] = num;
            count++;
        }
         */
        boolean[] choose = new boolean[n];
        dfs(choose, 0, n, nums);
        return count;
    }
    private void dfs(boolean[] choose, int cur, int n, int[] nums){
        if(cur == n){
            int ans = 0;
            for (int i = 0; i < n; i++) {
                if(choose[i]){
                    ans |= nums[i];
                }
            }
            if(ans > max){
                max = ans;
                count = 1;
            }else if(ans == max){
                count++;
            }
        } else {
            choose[cur] = true;
            dfs(choose, cur + 1, n, nums);
            choose[cur] = false;
            dfs(choose, cur + 1, n, nums);
        }
    }
}

/*
时间o(2^n)
static int count = 0;
    static int max = Integer.MIN_VALUE;
    public int countMaxOrSubsets(int[] nums) {

        if(nums.length == 1){
            return 1;
        }
        count = 0;
        max = Integer.MIN_VALUE;

int n = nums.length;

    dfs(0 , 0, n, nums);
        return count;
                }
private void dfs(int val, int cur, int n, int[] nums){
        if(cur == n){

        if(val > max){
        max = val;
        count = 1;
        }else if(val == max){
        count++;
        }
        } else {
        dfs(val | nums[cur], cur + 1, n, nums);
        dfs(val, cur + 1, n, nums);
        }
        }
 */